package arithmetic_40;

import java.util.LinkedList;
import java.util.Queue;

public class Solution_3 {

	/**
	 * 思路1：BFS解法 ->套用BFS模板代码（ali.Solution_5）
	 */
	public int maxDepth(TreeNode root) {

		if (root == null) {
			return 0;
		}

		Queue<TreeNode> queue = new LinkedList();
		queue.offer(root);

		int maxDepth = 0;
		while (!queue.isEmpty()) {
			int currentLevelSize = queue.size(); //从队列大小可以知道，当前层级有多少个元素
			for (int i = 0; i < currentLevelSize; i++) {
				// 获取并移除队头元素
				TreeNode treeNode = queue.poll();

				// 检查是否存在左右子节点，存在则入队列
				if (treeNode.left != null) {
					queue.offer(treeNode.left);
				}
				if (treeNode.right != null){
					queue.offer(treeNode.right);
				}
			}
			maxDepth++; // 深度+1
		}
		return maxDepth;
	}

	/**
	 * 思路2：DFS解法
	 */
	public int maxDepth2(TreeNode root) {

		// 递归终止条件
		if (root == null) {
			return 0;
		}

		/**
		 *  DFS分治：
		 *  1、先计算左节点和右节点的最大深度
		 *  2、然后取较大的值
		 *  3、最后再加上当前节点（当前节点也要算一层）
		 */
		return 1 + Math.max(maxDepth2(root.left), maxDepth2(root.right));

	}

	
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
}